package org.leetcode.difficulty;

import org.junit.Test;

public class FindMedianSortedArrays {
    public double findMedianSortedArrays(int[] num1, int[] num2) {
        // 要求是时间复杂度是O(log(m + n)), 所以应该使用二分查找
        // 找第k小的数
        int m = num1.length;
        int n = num2.length;
        int left = (m + n + 1) / 2;
        int right = (m + n + 2) / 2;
        //既然是二分查找，最好用递归
        return (find(num1, num2, 0, 0, left) + find(num1, num2, 0, 0, right) ) / 2.0;
    }

    /**
     *
     * @param num1 短数组
     * @param num2 长数组
     * @param aStart 长数组的开始位置
     * @param bStart 短数组的开始位置
     * @param k 第k小的数
     * @return 中位数
     */
    private double find(int[] num1, int[] num2, int aStart,int bStart, int k) {
        int len1 = num1.length - aStart;
        int len2 = num2.length - bStart;
        if(len1 > len2) {
            return find(num2, num1, bStart, aStart, k);
        }
        if(len1 == 0) {
            return num2[bStart + k - 1];
        }
       // 递归结束条件
       if(k == 1) {
           return Math.min(num1[aStart], num2[bStart]);
       }
       int i = aStart + Math.min(k / 2, len1) - 1;
       int j = bStart + Math.min(k / 2, len2) - 1;
       if(num1[i] < num2[j]) {
           return find(num1, num2, i + 1, bStart, k - (i - aStart + 1));
       } else {
           return find(num1, num2, aStart, j + 1, k - (j - bStart + 1));
       }

    }

    @Test
    public void test() {
        int[] num1 = new int[]{1};
        int[] num2 = new int[]{2, 3, 4, 5, 6};
        System.out.println(findMedianSortedArrays(num1, num2));
    }
}
